package test;

import java.util.ArrayList;
import java.util.List;

public class Subsets1 {
	public List<List<Integer>> ret;
    public List<Integer> path;
    public boolean[] check;
    public void dfs(int[] nums,int pos){ 
      //直接收集
      ret.add(new ArrayList(path));
      if(path.size()==nums.length){
        return ;
      }
      //i=pos，只能枚举当前位置pos往后的元素
      for(int i=pos;i<nums.length;i++){
        if(check[i]==false){
          path.add(nums[i]);
          check[i]=true;
          dfs(nums,i+1);
          //恢复现场
          check[i]=false;
          path.remove(path.size()-1);
        }
      }
    }
    public List<List<Integer>> subsets(int[] nums) {
        ret=new ArrayList<>();
        path=new ArrayList();
        check=new boolean[nums.length];
        dfs(nums,0);
        return ret;
    }
}
